package com.zhugang.week13.recursion;

/**
 * @program algorithms
 * @description: reverseList
 * @author: chanzhugang
 * @create: 2022/11/17 16:07
 */
public class ReverseList {

    /**
     * 剑指offer 24 反转链表
     * https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        /**
         * 递归到最底层，指针反转，画个图
         * O(n)，画图分析，线性的
         */
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newNode = reverseList(head.next);
        // 归的时候处理反转
        head.next.next = head;
        head.next = null;
        return newNode;
    }

    public ListNode reverseList2(ListNode head) {
        /**
         * 迭代反转：头插法，定义新的节点
         */
        ListNode newNode = null;
        ListNode currNode = head;
        while (currNode != null) {
            ListNode next = currNode.next;
            // 头插法套路
            currNode.next = newNode;
            newNode = currNode;
            currNode = next;
        }
        return newNode;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}